﻿//力扣：371. 两整数之和
//https://leetcode.cn/problems/sum-of-two-integers/description/


//方法一：简单求和，通俗易懂
//时间复杂度：O(1)
class Solution {
public:
    int getSum(int a, int b) 
    {
        return a + b;
    }
};




//方法二：位运算
//时间复杂度：O(1)

//算法原理：
//◦ 异或^ 运算本质是「⽆进位加法」；
//◦ 按位与& 操作能够得到「进位」；
//◦ 然后⼀直循环进⾏，直到「进位」变成 0 为⽌。

//思路概述
//在计算机科学中，加法可以通过位操作来实现。这里使用了两种位操作：
//1. 异或操作(^)：用于计算不带进位的加法。
//2. 与操作(&) 加左移：用于计算进位。
//通过这两种操作，逐步将进位加到结果中，直到进位为零。
class Solution {
public:
    int getSum(int a, int b) 
    {
        while (b)                               // 当 b 为 0 时，表示没有进位了，可以终止循环
        { 
            int x = a ^ b;                      // 第一步：计算不带进位的加法结果
            unsigned int carry = (unsigned int)(a & b) << 1;  // 第二步：计算进位并左移一位
            a = x;                              // 更新 a 为当前的加法结果
            b = carry;                          // 更新 b 为当前的进位
        }

        return a;                               // 当进位为 0 时，a 就是最终结果
    }

};
//1. 为什么 while (b) 判断可以终止循环
//在这段代码中，b 并不是一成不变的。b 是逐步更新的，每次循环中，b 被赋值为(a & b) << 1，即表示“进位”。
//因此，b 一开始是传入的 b，但在每轮循环后，它被更新为当前运算的进位信息。当 b 为 0 时，说明已经没有进位需要处理了，此时加法已经完成，所以可以终止循环。
//换句话说，while(b) 的判断实际上是在检测“是否还有进位”。如果(a & b) << 1 为 0，则表示没有进位，即 b 会变成 0，从而退出循环。
//因为 b 的值每次都更新，因此判断 while (b) 能准确判断加法是否完成。
//
//2. 为什么使用 unsigned int
//使用 unsigned int 的原因是为了避免左移操作导致的符号位问题。在 C++ 中，如果 a 和 b 是 int 类型，进行位操作时可能会产生负数，尤其是在处理进位左移的过程中。
//具体而言，如果进位结果大于 INT_MAX，左移操作可能会导致符号位变化，产生未定义行为（在 C++ 中，对有符号整数的左移操作未定义）。
//通过将 carry 定义为 unsigned int 类型，可以确保左移后的进位值是无符号的，从而避免符号位干扰。
//例如，当进位值较大（接近或超过符号位的范围）时，unsigned int 保证了我们处理的是正数逻辑，避免因符号变化导致的错误结果。
//
//3. 为什么 while (b == 0) 后 a 是正确答案
//整个算法基于以下两点性质：
//
//    · 异或运算(^) 实现了无进位加法：每次 a^ b 计算出的是 a 和 b 的无进位加法结果。
//    · 与运算(&) 和左移模拟进位：(a & b) << 1 计算出需要进位的部分，并将其左移一位，放到进位正确的位置。
//在每一轮中，a 被更新为无进位加法结果，b 被更新为进位。这样经过多轮计算后，当进位 b 为 0 时，说明不再有进位需要处理了，此时 a 中就已经包含了最终的加法结果。
//
//这是因为：
// · 无进位部分和进位部分最终会合并：每一轮计算中，a 和 b 都在不断地合并无进位部分和进位部分，直到进位部分完全消失。
// · 最终得到的 a 就是 a + b 的值，因为无进位加法和进位已经被正确合并到了一起。
//因此，当 b 为 0 时，a 已经是正确的最终加法结果。
//
//总结
//while (b) 判断的是进位是否为 0。
//unsigned int 确保左移操作不受符号位影响，避免错误。
//退出循环时，a 是正确的加法结果，因为无进位和进位都已正确合并。